package bintree.leetcode;

import java.util.*;

/**
 * @Author: yuisama
 * @Date: 2021/9/3 16:11
 * @Description:二叉树的前序遍历 https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
 * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 */
public class Num144_PreOrder {
    //    /**
//     * 思路二 : 不借助任何其他函数和变量，在当前函数内部实现问题拆解
//     * 二叉树的前序遍历结果 = 根节点的值 + 左子树的结果集 + 右子树的结果集
//     * @param root
//     * @return
//     */
//    public List<Integer> preorderTraversal(TreeNode root) {
//        List<Integer> res = new ArrayList<>();
//        if (root == null) {
//            return res;
//        }
//        res.add(root.val);
//        // 再添加左子树的结果集，结果存在递归函数的返回值中
//        res.addAll(preorderTraversal(root.left));
//        // 再添加右子树的结果集
//        res.addAll(preorderTraversal(root.right));
//        return res;
//    }
//    List<Integer> retList = new ArrayList<>();
//    // 迭代实现，借助栈
//    public List<Integer> preorderTraversal(TreeNode root) {
//        Stack<TreeNode> nodeStack = new Stack<>();
//        if (root == null) {
//            return retList;
//        }
//        nodeStack.push(root);
//        // 当节点栈中还存在元素，说明树的遍历还未结束
//        while (!nodeStack.isEmpty()) {
//            // 取出栈顶元素
//            TreeNode node = nodeStack.pop();
//            // 访问根节点
//            // 因为栈的结构是先进后出，因此现将右子树入栈
//            retList.add(node.val);
//            if (node.right != null) {
//                nodeStack.push(node.right);
//            }
//            // 访问左子树
//            if (node.left != null) {
//                nodeStack.push(node.left);
//            }
//        }
//        return retList;
//    }
    // 递归实现
//    public List<Integer> preorderTraversal(TreeNode root) {
//        // 终止条件
//        if (root == null) {
//            return retList;
//        }
//        // 先访问根节点
//        retList.add(root.val);
//        // 先访问左子树
//        preorderTraversal(root.left);
//        // 再访问右子树
//        preorderTraversal(root.right);
//        return retList;
//    }
}
